import java.util.ArrayList;
import java.util.Arrays;

public class HashBuck {
    private static class Node{
        private int key;
        private int val;
        private Node next;

        private Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    private Node[] arr;
    private int sz;
    private static double loadFactor=0.75;

    public HashBuck() {
        this.arr = new Node[10];
    }

    public void put(int key,int val){
        int index = key%arr.length;
        if(arr[index]==null) {
            arr[index] = new Node(key, val);
        }
        else{
            Node cut = arr[index];
            while(cut.next!=null){
                if(cut.key==key){
                    cut.val=val;
                    return;
                }
                cut=cut.next;
            }
            cut.next= new Node(key, val);
        }
        sz++;
        fz();
    }

    private void fz(){
        double a = sz*1.0/arr.length;
        if(a>=loadFactor){
            //arr= Arrays.copyOf(arr,arr.length*2);
            Node[] newArr = new Node[2* arr.length];
            for (int i = 0; i < arr.length; i++) {
                Node cut1 = arr[i];
                while(cut1!=null){
                    int index = cut1.val% newArr.length;
                    if(newArr[index]==null) {
                        newArr[index] = new Node(cut1.key, cut1.val);
                    }
                    else{
                        Node cut = arr[index];
                        while(cut.next!=null){
                            if(cut.key==cut1.key){
                                cut.val=cut1.val;
                            }
                            cut=cut.next;
                        }
                        cut.next= new Node(cut1.key, cut1.val);
                    }
                    cut1=cut1.next;
                }
            }
            arr=newArr;
        }
    }
    public int get(int key){
        int index = key% arr.length;
        Node cut = arr[index];
        while(cut!=null){
            if(cut.key==key)
                return cut.val;
            else
                cut=cut.next;
        }
        return -1;
    }
}
